package cn.z2huo.algorithm.greedy.MiniSpanTree;

/*
*   最小生成树算法
*   Prim 算法
*   其中有一个集合，来表示已经生成的生成树，然后向该集合中不断地添加元素，
*   有一个数组，lowcost数组，用来存储集合中现有元素距离其他元素的最短距离，
*   有一个数组，farArray，用来存储各个节点的父节点，在其中的某个值被初始化时，
*   不一定是最短的路径，可能还有更短的，之后会进行更新
*
*   不断地向集合中添加元素，然后更新lowcost中的数值
*
* */

public class Prim {
    // max用来标示图中连个元素无连接时的状态
    static int max = 100;

    // 算法主体
    public int prim(int[][] mapArray, int[] farArray){
        int[] lowcost = new int[6];
        initArray(lowcost, 0);
        int sum = 0;

        // 以mapArray[0]为根节点，初始化最低权值数组（为mapArray）中的第一行
        for(int i=0; i<mapArray[0].length; i++){
            lowcost[i] = mapArray[0][i];
        }

        // 要连接 mapArray.length-1 个节点，遍历相同次数
        for(int i=1; i<mapArray.length; i++){
            // 这两个元素用来记录当前 lowcost 中最小路径值的位置以及数值
            int minId = 0, minValue = max;
            // 遍历lowcost，找出最小值
            for (int j=0; j<mapArray[i].length; j++){
                if(lowcost[j]!=0 && lowcost[j]<minValue){
                    minId = j;
                    minValue = lowcost[j];
                }
                if(i==1){
                    farArray[0] = minId;
                }
            }

            // 计算路径综合，加上上面找到的最短路径
            sum += minValue;
            printArray(lowcost);
            // 因为已经加入到集合中，所以将该位置置为零，表示该元素已经连接过了
            lowcost[minId] = 0;
            // 上面向集合中添加了一个新的元素，为了找出更新后的集合中的元素距离集合外元素的距离
            // 将原来lowcost中的路径值与新加入的这个元素的路径值比较，取更小的，放到lowcost中
            for (int j=0; j<mapArray[i].length; j++){
                if(mapArray[minId][j]!=0 && mapArray[minId][j]<lowcost[j]){
                    lowcost[j] = mapArray[minId][j];
                    // 如果在lowcost中某个位置发生了更新
                    // 则更新farArray中对应位置的值为刚刚加入到集合中的元素的 id（minId）
                    // 注意此时farArray中的值只是暂时的，表示在当前集合中应该对应的父元素id，
                    // 之后再向集合中添加元素，farArray中的值有可能被覆盖，因为产生了更短的路径（权值）
                    farArray[j] = minId;
                }
            }
        }
        return sum;
    }

    // 用来初始化二维数组
    public void initArray(int[] array, int num){
        for(int i=0; i<array.length; i++){
            array[i] = num;
        }
    }
    // 输出一维数组
    public void printArray(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%4d", array[i]);
        }
        System.out.println();
    }
    // 输出二维数组
    public void printArray(int[][] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.printf("%4d", array[i][j]);
            }
            System.out.println();
        }
    }
    // 用于输出路径数组
    public void printRoad(int[] farArray){
        for(int i=0; i<farArray.length; i++){
            if(farArray[i] != 0){
                System.out.printf("%d ---- %d \n", i+1, farArray[i]+1);
            }
        }
    }

    public static void main(String[] args){
        int[][] mapArray = {
                {0,6,1,5,max,max},
                {6,0,5,max,3,max},
                {1,5,0,5,6,4},
                {5,max,5,0,max,2},
                {max,3,6,max,0,6},
                {max,max,4,2,6,0}
        };
        int[] farArray = new int[6];
        int sum = 0;

        Prim p = new Prim();
        System.out.println("表示无向连通带权图的矩阵是"+"（其中"+max+"表示的是两个节点之间没有连接）：");
        p.printArray(mapArray);
        System.out.println("表示距离集合最小权值的数组为：");
        sum = p.prim(mapArray, farArray);
        System.out.println("最小生成树为：");
        p.printRoad(farArray);
        System.out.println("最小生成树的权值和为： \n"+sum);
    }
}
